Class III histone deacetylases (Sir2 or sirtuins) catalyze the NAD+-dependent conversion of acetyl-lysine residues to nicotinamide, 2'-O-acetyl-ADP-ribose (OAADPr), and deacetylated lysine. Class I and II HDACs utilize a different deacetylation mechanism, utilizing an active site zinc to direct hydrolysis of acetyl-lysine residues to lysine and acetate. Here, using ten acetyl-lysine analog peptides, we have probed the substrate binding pockets of sirtuins and investigated the catalytic differences among sirtuins and class I and II deacetylases. For the sirtuin Hst2, acetyl-lysine analog peptide binding correlated with the hydrophobic substituent parameter pi with a slope of -0.35 from a plot of log Kd versus pi. Interestingly, propionyl- and butyryl-lysine peptides were found to bind tighter to Hst2 compared with acetyl-lysine peptide and showed measurable rates of catalysis with Hst2, Sirt1, Sirt2, and Sirt3, suggesting propionyl- and butyryl-lysine proteins may be sirtuin substrates in vivo. Unique among the acetyl-lysine analog peptides examined, homocitrulline peptide produced ADP-ribose instead of the corresponding OAADPr analog. The electron-withdrawing nature of each acetyl analog had a profound impact on the deacylation rate between deacetylase classes. The rate of catalysis with the acetyl-lysine analog peptides varied over five orders of magnitude with the class III deacetylase Hst2, revealing a linear free energy relationship with a slope of -1.57 when plotted versus the Taft constant, sigma*. HDAC8, a class I deacetylase, displayed the opposite trend with a slope of +0.79. These results are applicable toward the development of selective substrates and other mechanistic probes of protein deacetylases.